Iterative: Find

First, we need a structure for our nodes and a way to search the tree.

The Node class is our fundamental building block, holding a key and pointers to left and right children.
The find function starts at the root and iteratively moves down the tree.
At each node, it compares the target key with the current node's key to decide whether to go left, go right, or stop.
The search ends when the key is found or when it hits a None pointer (a dead end), meaning the key is not in the tree.

# A class to represent a single node in the BST.
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def find(root, key):
    """Searches for a key in the BST using a while loop."""
    current = root
    while current is not None:
        if key < current.key:
            # The target key is smaller, so go left.
            current = __________
        elif key > current.key:
            # The target key is larger, so go right.
            current = __________
        else:
            # We found the key!
            return True

    # Reached a None, so the key was not found.
    return __________

Copied!